package org.example.struct.array;

import java.util.*;

/**
 * @author liyishan
 * @date 2023/12/26 09:35
 * @apiNote
 */

public class Test00690GetImportance {

    public int getImportance(List<Employee> employees, int id) {
        Map<Integer,Employee> map = new HashMap<>();
        for(Employee e: employees){
            map.put(e.id,e);
        }
        return dfs(id,map);
    }

    private int dfs(int id,Map<Integer,Employee> map){
        Employee employee = map.get(id);
        int total = employee.importance;
        List<Integer>  subordinates = employee.subordinates;
        for(int subId : subordinates){
            total += dfs(subId,map);
        }
        return total;
    }

    public int getImportance1(List<Employee> employees, int id) {
        Map<Integer,Employee> map = new HashMap<>();
        for(Employee e: employees){
            map.put(e.id,e);
        }
        int total = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);
        while(!queue.isEmpty()){
            int curId= queue.poll();
            Employee employee = map.get(curId);
            total += employee.importance;
            List<Integer> subordinates = employee.subordinates;
            for(int subId : subordinates){
                queue.offer(subId);
            }
        }
        return total;
    }




    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    }
}
